package easy;

/**
 * @author gh
 * @create 2021-05-30 20:40
 */
public class lee159_fib {

    //recursion
    public int fib(int n) {
        if(n<1)
            return 0;
        if(n==1)
            return 1;

        return fib(n-1)+fib(n-2);
    }


    //动态规划
    public int fib2(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

}
